package com.sheng.leetcode.year2022.month12.day12;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/12/12
 * <p>
 * 1781. 所有子字符串美丽值之和<p>
 * <p>
 * 一个字符串的 美丽值 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。<p>
 * 比方说，"abaacc" 的美丽值为 3 - 1 = 2 。<p>
 * 给你一个字符串 s ，请你返回它所有子字符串的 美丽值 之和。<p>
 * <p>
 * 示例 1：<p>
 * 输入：s = "aabcb"<p>
 * 输出：5<p>
 * 解释：美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ，每一个字符串的美丽值都为 1 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：s = "aabcbaa"<p>
 * 输出：17<p>
 * <p>
 * 提示：<p>
 * 1 <= s.length <= 500<p>
 * s 只包含小写英文字母。<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/sum-of-beauty-of-all-substrings">1781. 所有子字符串美丽值之和</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1781 {

    @Test
    public void test01() {
//        String s = "aabcb";
        String s = "aabcbaa";
        System.out.println(new Solution().beautySum(s));
    }
}

class Solution {
    public int beautySum(String s) {
        // 获取字符串 s 的所有子串，题目要求，必须有两种以上的字符才有美丽度这一概念
        int ans = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            int[] nums = new int[26];
            int max = 0;
            for (int j = i; j < length; j++) {
                nums[s.charAt(j) - 'a']++;
                max = Math.max(max, nums[s.charAt(j) - 'a']);
                int min = s.length();
                for (int num : nums) {
                    if (num > 0) {
                        min = Math.min(min, num);
                    }
                }
                ans += max - min;
            }
        }
        return ans;
    }
}
